// 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

// 示例 1 :

// 输入:nums = [1,1,1], k = 2
// 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
// 说明 :

// 数组的长度为 [1, 20,000]。
// 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

#include <vector>
#include <unordered_map>

using namespace std;

/* 以i开头
时间复杂度：O(n^2)
空间复杂度：O(1)
*/
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int res{0};
        for (int i{0}; i < n; ++i) {
            int sum{0};
            for (int j{i}; j < n; ++j) {
                sum += nums[j];
                if (sum == k) {
                    ++res;
                }
            }
        }
        return res;
    }
};

/* 以i结尾
时间复杂度：O(n^2)
空间复杂度：O(1)
*/
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int res{0};
        for (int i{0}; i < n; ++i) {
            int sum{0};
            for (int j{i}; j >= 0; --j) {
                sum += nums[j];
                if (sum == k) {
                    ++res;
                }
            }
        }
        return res;
    }
};

/* 前缀和 + 哈希表优化
考虑以 i 结尾的和为 k 的连续子数组个数时只要统计有多少个前缀和为 pre[i]−k 的 pre[j]
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash{};
        hash[0] = 1;
        int sum{0}; // 前缀和
        int res{0};
        for (int& num : nums) {
            sum += num;
            if (hash.find(sum - k) != hash.end()) {
                res += hash[sum - k];
            }
            ++hash[sum];
        }
        return res;
    }
};

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> sums(n, nums[0]);
        for (int i{0}; i < n; ++i) {
            sums[i] = sums[i-1] + nums[i];
        }
        int res{0};
        for (int i{0}; i < n; ++i) {
            if (nums[i] == k) ++res;
            for (int j{i + 1}; j < n; ++j) {
                if (sums[j] - sums[i] == k) ++res;
            }
        }
        return res;
    }
};